package com.interview.javabase.algorithm;

import org.junit.Test;
import org.springframework.boot.test.context.SpringBootTest;

/**
 * @description: 有n步台阶，一次只能上1步或2步，共有多少种走法？
 * f(1) = 1
 * f(2) = 2
 * f(3) = f(2) + f(1)
 * f(4) = f(3) + f(2)
 * f(n) = f(n-1) + f(n-2)
 * @author: zhangshuguang@vichain.com
 * @date: 2019/06/12 15:19
 */
@SpringBootTest
public class Demo15 {

    @Test
    public void solution1() {

        System.out.println(step(10));
        System.out.println(stepLoop(10));
    }

    private int step(int n){
        if (n == 1){
            return 1;
        }

        if (n == 2){
            return 2;
        }

        return step(n -1) + step(n -2);
    }

    private int stepLoop(int n){
        if (n == 1){
            return 1;
        }

        if (n == 2){
            return 2;
        }

        int sumStep = 0;
        int i = 1; // n - 2
        int j = 2; // n - 1

        for (int k = 3; k <= n; k++) {
            sumStep = (i + j);
            i = j;
            j = sumStep;
        }

        return sumStep;
    }

}
